Euclid's Lemma

While Euclid's theorem is the name generally given to the result further down this page, here we prove a generalised version first.

Proof

Suppose \(n, a, b \in \mathbb{Z}\) with \(n \mid ab\) and \(\gcd(a, n) = 1\). From the Bezout identity we know that there exists an \(x, y \in \mathbb{Z}\) such that \(ax + ny = 1\). Multiplying through by \(b\) we have that

Then \(n \mid ab \implies n \mid abx\) and similarly \(n \mid nby\) so \(n \mid abx + nby = b\) as required.

This is the definition of a prime element in a ring, the fact that the definition of a prime number implies that these numbers are prime elements depends on the integers being a unique factorisation domain, a fact which is proven using this. As such, Euclid's lemma here is proven as an independent fact.

Proof

Suppose \(p\) is prime and that \(p \not\mid a\). Then \(\gcd(p, a) = 1\) since the only factors of \(p\) and \(1\) and \(p\), of which \(p\) is not a factor of \(a\). Hence by the generalised result \(p \mid b\). Likewise if we assume \(p \not\mid b\).